1. Field of the Invention
The present invention relates to an automated compaction system for repositioning cell instances within an integrated circuit (IC) layout to reduce IC floor space, and more particularly to a compaction system that also modifies the internal layouts of the cell instances.
2. Description of Related Art
An integrated circuit (IC) fabricator typically manufactures an IC by doping a semiconductor substrate to form a pattern of rectilinear doped areas of various sizes and shapes and then successively laying down several layers of various types of material over the substrate, with each layer being etched or deposited to form a pattern of rectilinear shapes. An IC designer produces an IC design in the form of an IC layout, a data file describing the substrate doping pattern and the patterns for each layer of material above the substrate, and the IC manufacturer uses the layout as a guide for fabricating the IC.
The rectilinear areas of doped semiconductor substrate and the other rectilinear objects formed on the higher layers of the IC form electronic devices such as transistors, capacitor and resistors, and also form conductors for interconnecting the devices. An IC designer will usually create an IC initially in the form of a netlist describing an IC at a relatively high level of abstraction; for example, by a set of Boolean expressions describing the logic the IC is to carry out. The designer will then employs various automated tools to covert the high level netlist into a gate level netlist describing the IC as a collection of interconnected instances of standard cells, where each cell describes the layout of a device such as a transistor, a capacitor, a resistor, a logic gate or other device. The gate level netlist also indicates which terminals of the cells are to be interconnected by conductive nets. The gate level netlist describes each cell instance only indirectly by referring it as an instance of a standard cell described in a cell library. The designer then uses a computer-aided placement and routing tool to generate the IC layout based on the gate level netlist. The placement and routing tool automatically determines how to position and orient each cell within the layout for each cell instance and how to form the nets interconnecting them from objects on various layers of the IC. The placement and routing tool obtains the internal layout for each cell instance from the cell library.
A designer may use graphic tools to manually generate a layout for a custom devices not included in the cell library, thereby creating a new cell for a cell library. The new cell may be hierarchical in that it incorporates instances of existing cells. For example a new gate cell may incorporate instances of various types of existing transistor cells.
After creating an initial layout for a portion of an IC, for an entire IC, or for a new IC cell, the designer will sometime use a computer-aided compaction tool (a compactor) 10 as illustrated in FIG. 1 to modify the initial layout 11 by repositioning cells and the nets that interconnect them to produce a compacted layout 12 that takes up less floor space within an IC. For example FIG. 2 shows how compactor 10 might convert a simple, initial layout 11 having four cells A-D interconnected by nets 15 to produce a compacted IC layout 12 where the cells are closer together.
When compacting the initial layout 11, compactor 10 must ensure that that compacted layout 12 satisfies a set of design rules 17 imposed by the IC fabricator that place limits on the dimensions of and spacing between objects formed on the various layers of the IC. For example, as shown in FIG. 3, a design rule may specify a minimum distance d1 between two objects A and B on the same layer of a layout, or a minimum dimension d2 for an object A as shown in FIG. 4. As illustrated in FIG. 5, a design rule may specify that the edges of object A on one layer of the IC residing above another object B must be horizontally spaced from the edges object B residing on another layer of the IC by some minimum distance d3.
Such design rules 17 place constraints on how a compactor 10 can reposition cells A-D and nets 15 of initial layout 11 of FIG. 2 when forming the compacted IC layout 12. Since various objects subject to design rule constraints form the cell instances and nets, a compactor risks violating design rules by moving cell instances closer together. For example, FIG. 6A shows a cell instance 36 formed by a set of objects 38-43 positioned near another object 44 within a layout. Design rules might subject the distance between the material forming objects 40 and 44 to a minimum spacing constraint. A compactor might therefore move cell instance 36 closer to object 44 as illustrated in FIG. 6B, but no closer than the point at which the spacing between objects 40 and 44 satisfies the minimum spacing constraint d1 between objects 40 and 44 as illustrated in FIG. 6B. Note that in doing so, the compactor causes objects 38 and 44 to overlap, but this is permissible when no design rule prohibits overlap of the material forming objects 38 and 44. Thus a compactor must take into account the internal layout of each instance cell when compacting a layout to make sure that in bringing cell instances closer together it does not violate design rules limiting the spacing between objects forming those cell instances. However a conventional compactor does not reposition objects within a cell instance because the relative positions of objects forming a cell instance can influence the electrical behavior of the cell instance.
As illustrated in FIG. 7, a typical compactor uses a two-phase process to compact a layout, by first compacting the layout in an X direction within the plane of the IC layout and then compacting the layout in an orthogonal Y direction. The compactor initially (step 20) builds a graph modeling the relative position of the object boundaries along the X direction and indicating the minimum spacing between edges mandated by the design rules. It then uses well-known graph theory techniques to “solve the graph” (step 22) by finding a position for each edge that maximizes the amount of layout compression in the X direction while satisfying the design rules. The compactor then converts the graph solution into a new layout compressed in the X direction. Using the x-direction compressed layout as input, the compactor then repeats the process to compress the layout in the Y direction, building graph modeling the relative positions of edges in the Y direction (step 26), solving that graph (step 28) and then converting the graph solution back into a layout that is compressed in both the X and Y directions (step 30).
FIG. 8 shows a simple example of an uncompressed layout having four objects A-D residing in a placement area having X-direction boundaries S1 and S2. Object A has X-direction boundaries A1 and A2, object B has X-direction boundaries B1 and B2, object C has X-direction boundaries C1 and C2, and object D has X-direction boundaries D1 D2. The design rules specify minimum spacings between edges of the objects in the layout, and the double arrows in FIG. 8 extend between edges that are subject to minimum spacing design rules. The number above each double arrow indicates a minimum space between the objects permitted by the design rules. Thus edges A2 and D1 must be at least one unit apart, edges A2 and C1 must be at least one unit apart, and edges B2 and C1 must be at least one unit apart. In this example, all of the objects are two dimension units wide.
In carrying out step 20 of FIG. 7, the compactor generates a graph as illustrated in FIG. 9 in which the edges S1 and S2 of the placement area, and the edges A1, A2, . . . D1, D2 of the objects correspond to nodes of the graph, arrows (directed vertices of the graph) represent spatial relationships between edges, with a number next to each edge indicating the minimum allowable spacing between the edges. A number next to each node indicates the current position of the edge corresponding to the node in the X-direction.
As it solves the graph (step 22 of FIG. 7), the compactor tries to find a coordinate for each node that will minimize the distance between S1 and S2. However in doing so, the compactor must not change the width of any object and must ensure that the spacing between object edges satisfies the design rules.
FIG. 10 shows a solution to the graph of FIG. 9 providing minimum spacing between edges. The graph of FIG. 10 shows that the compactor should move objects B and C one unit in the −X direction, and should move object D two units in the −X direction. This will allow the compactor to move area edge S2 two units in the −X direction as illustrated in FIG. 11, thereby shrinking the placement area from 7 units wide to 5 units wide when the compactor modifies the layout (step 24 of FIG. 7) in accordance with the solution graph of FIG. 11.
The compactor next processes the new X direction compacted layout (step 26 of FIG. 7) to produce a graph modeling edge positions in the Y direction. FIG. 12 shows the labeling of object area edges associated with the nodes of the resulting graph for use in connection with Y-direction compaction. FIG. 13 shows a Y-direction graph modeling the layout of FIG. 12, and FIG. 14 illustrates the solution to the graph of FIG. 13 the compactor produces at step 28 of FIG. 7. FIG. 15 illustrates the resulting layout the compactor produces at step 30 of FIG. 7 that has been compacted in both the X and Y directions.
U.S. Pat. No. 6,587,992, issued Jul. 1, 2003 to Marple describes a two-dimensional compaction system the carries out compaction in both X and Y directions at the same time.
While prior art compactors can compact an IC layout by repositioning cells in a manner consistent with design rules, or by replacing cells, the amount by which they can compact a layout is limited by the need to maintain adequate spacing between cells and by the dimensions and internal layouts of the individual cells incorporated into the design. U.S. Pat. No. 6,446,239 issued Sep. 3, 2002 teaches to replace some of the cells within an IC layout when doing so can help reduce the dimensions of an IC layout. However here too, the dimensions and internal layouts of available cells limit the ability of the compaction system to compact the layout.